class Solution {
public:
    TreeNode* _build(vector<int>& preorder, vector<int>& inorder,
        int& prei, int inbegin, int inend)
    {
        if (inbegin > inend)
            return nullptr;

        TreeNode* root = new TreeNode(preorder[prei]);
        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (preorder[prei] == inorder[rooti])
                break;
            ++rooti;
        }
        //[inbegin,rooti-1] rooti [rooti+1,inend]
        ++prei;
        root->left = _build(preorder, inorder, prei, inbegin, rooti - 1);
        root->right= _build(preorder, inorder, prei, rooti + 1,inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
       return _build(preorder,inorder, i, 0, inorder.size() - 1);
        
    }
};

